1. Field of the Invention
The present invention relates to a moving image compression technique, and in particular to an image motion detection device for detecting the motions of an image which derives a motion vector for each of a plurality of blocks included in the image.
2. Description of the Related Art
In the field of moving image compression technology, a block matching method is widely used, according to which an image is divided into blocks each consisting of N.times.N pixels and a motion vector is derived for each block.
FIG. 14 illustrates the concept of the block matching method. Specifically, FIG. 14 describes an operation in which a current image 1 is divided into blocks 3, and a region having a similarity to each block 3 is searched for in a reference image 2. The motion vector for each block 3 is obtained by using pixel values C.sub.x,y of the current image and the pixel values R.sub.x,y of the reference image to derive a prediction error E(p,q) for each candidate motion vector (p,q) in accordance with eq.1, and selecting as a motion vector 4 the candidate motion vector (p,q) that has the minimum prediction error E(p,q). Hereinafter, this operation will be referred to as a "motion vector search". It is assumed that a motion vector search is conducted under the conditions .vertline.p.vertline., .vertline.q.vertline..ltoreq.L. Herein, L is an integer. EQU .SIGMA.(p,q)=.SIGMA..sub.x.sup.N.sub.=1 .SIGMA..sub.y.sup.N.sub.=1 .vertline.C.sub.x,y --R.sub.x+p, y+q .vertline.
When compressing a moving image, in general, the quality of the image obtained by decompressing a compressed image improves as the prediction error of the motion vector decreases. Therefore, an exhaustive search method, which searches all the candidate motion vectors in a given area, is the most advantageous in terms of the quality of the reconstructed image.
FIG. 15 illustrates a motion vector search by the exhaustive search method in the case where L=7. As seen from FIG. 15, the search is directed to all of the points (p, q) in the area, that is, all of the points (p, q) in the area are used as candidate motion vectors. In this example, the number of candidate motion vectors per block is 225, indicative of a large amount of computation to be performed for the calculation of prediction errors.
Therefore, various algorithms of motion vector searching have been proposed for reducing the computation amount required for the detection of motion vectors by limiting the number of candidate motion vectors. Among such methods, a "step search" method is particularly well-known.
FIG. 16 illustrates a motion vector search by a three-step search method in the case where L=7. The three-step search method is performed in the following procedure.
Step 1: Prediction errors are derived for 9 candidate motion vectors, i.e., an origin and 8 points which are away from the origin by .+-.4 pixels along the p direction and/or the q direction. A point corresponding to the one of the 9 candidate motion vectors that has the minimum prediction error is selected.
Step 2: Prediction errors are derived for 9 candidate motion vectors, i.e., the point selected in Step 1 and 8 points which are away from the point selected in Step 1 by .+-.2 pixels along the p direction and/or the q direction. A point corresponding to the one of the 9 candidate motion vectors that has the minimum prediction error is selected.
Step 3: Prediction errors are derived for 9 candidate motion vectors, i.e., the point selected in Step 2 and 8 points which are away from the point selected in Step 2 by .+-.1 pixel along the p direction and/or the q direction. A point corresponding to the one of the 9 candidate motion vectors that has the minimum prediction error is selected.
In this example, the number of candidate motion vectors per block is 25, which is 1/9 of the amount of computation required for the exhaustive search method.
A number of image motion detection devices in the prior art apply the same motion detection algorithm for each block. A method disclosed in Japanese Laid-Open Patent Publication No. 7-177519 applies a motion detection to some blocks while performing an interpolation for other blocks without applying any motion detection thereto.
FIG. 17 illustrates an example of "thinning out" blocks as disclosed in Japanese Laid-Open Patent Publication No. 7-177519. An image is divided into a plurality of blocks, which are classified into first blocks (shaded in FIG. 17) and second blocks. A motion detection is performed for any first block, but no motion detection is performed for any second block. Instead, the motion vector for the second block is obtained by interpolating the motion vectors for the blocks surrounding the second block.
Among the conventional motion vector search algorithms, the exhaustive search method is the most advantageous in terms of the quality of the reconstructed image, but has the problem of requiring a large amount of computation.
The step search method can substantially reduce the computation amount as compared to the exhaustive search method. However, since it does not process enough candidate motion vectors, it is possible that a motion vector with a large prediction error may be selected, resulting in poor quality of the reconstructed image.
According to the method disclosed in Japanese Laid-Open Patent Publication No. 7-177519, the motion vector for the "thinned-out" block is obtained by interpolating motion vectors for the blocks surrounding the "thinned-out" blocks. Therefore, as in the case of the step search method, the method in Publication No. 7-177519 can substantially reduce the computation amount as compared to the exhaustive search method, but may select a motion vector with a large prediction error, resulting in poor quality of the reconstructed image.